package a1sort.a4recursionsort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author zhangMr
 * @descripton
 * 根据算法导论第二章的分治策略自定的递归排序算法
 *期望运行时间n㏒n
 */
public class RecursionSort {
    //合并两个已经排好的数组
    public static void merge(int leftStartIndex,int leftEndIndex,int rightStartIndex,int rightEndIndex,Integer[] origianlData){
            int i=0;
            int j=0;
            int startInex=leftStartIndex;
            int lengthLeft=leftEndIndex-leftStartIndex+1;
            int lengthRight=rightEndIndex-rightStartIndex+1;

            Integer[] leftArr= Arrays.copyOfRange(origianlData, leftStartIndex, leftEndIndex+1);
            Integer[] rightArr= Arrays.copyOfRange(origianlData, rightStartIndex, rightEndIndex+1);
            while(true){
                int leftValue=leftArr[i];
                int rightValue=rightArr[j];
                if(leftValue>rightValue){
                    origianlData[startInex]=rightValue;
                    j++;
                    startInex++;
                }else if(rightValue>leftValue){
                    origianlData[startInex]=leftValue;
                    i++;
                    startInex++;
                }else{
                    origianlData[startInex]=leftValue;
                    startInex++;
                    origianlData[startInex]=rightValue;
                    startInex++;
                    i++;
                    j++;
                }
                if(i==lengthLeft){
                    if(j<lengthRight){
                        for(int k=j;k<lengthRight;k++){
                            origianlData[startInex]=rightArr[k];
                            startInex++;
                        }
                    }
                    break;
                }
                if(j==lengthRight){
                    if(i<lengthLeft){
                        for(int k=i;k<lengthLeft;k++){
                            origianlData[startInex]=leftArr[k];
                            startInex++;
                        }
                    }
                    break;
                }
            }
    }
    //递归调用
    public static void recursionSort(Integer[] data,Integer start,Integer end){
        if(start<end){
            int leftStartIndex=start;
            int leftEndIndex=(start+end)/2;
            int rightStartIndex=leftEndIndex+1;
            int rightEndIndex=end;
//            System.out.println(leftStartIndex+":"+leftEndIndex);
            recursionSort(data,leftStartIndex,leftEndIndex);
//            System.out.println(rightStartIndex+":"+rightEndIndex);
            recursionSort(data,rightStartIndex,rightEndIndex);
//            System.out.println("================================");
            merge(leftStartIndex, leftEndIndex, rightStartIndex, rightEndIndex,data);
        }else{
            return;
        }
    }

    public static void main(String[] args) {
        Random random=new Random();
        Integer[]data=new Integer[10];
        for(int i=0;i<10;i++){
            data[i]= random.nextInt(100);
        }
        System.out.println("随机生成的数组"+Arrays.toString(data));
        recursionSort(data,0,data.length-1);
        System.out.println("排序后的数组"+Arrays.toString(data));
    }
}
